package 学习;

import java.util.Arrays;

/**
 * Keafmd
 *
 * @ClassName: QuickSort
 * @Description: 快速排序
 * @author: 牛哄哄的柯南
 * @date: 2021-06-24 10:32
 */
public class QuickSort {

    //快速排序
    public static void quickSort(int[] arr) {
        quickSort(arr, true);
    }

    public static void quickSort(int[] arr, boolean ascending) {
        quickSort(arr, 0, arr.length - 1, ascending);
    }

    public static void quickSort(int[] arr, int begin, int end, boolean ascending) {
        if (begin >= end) { // 结束条件
            return;
        }
        int base = arr[begin];
        int i = begin, j = end;
        while (i < j) { // 两个哨兵（i左边，j右边）没有相遇
            if (ascending) { // 升序
                while (arr[j] >= base && i < j) { // 哨兵j没找到比base小的
                    j--;
                }
                while (arr[i] <= base && i < j) { // 哨兵i没找到比base大的
                    i++;
                }
            } else { // 降序
                while (arr[j] <= base && i < j) { // 哨兵j没找到比base大的
                    j--;
                }
                while (arr[i] >= base && i < j) { // 哨兵i没找到比base小的
                    i++;
                }
            }
            if (i < j) { // 如果满足条件则交换
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // 最后将基准与i和j相等位置的数字交换
        arr[begin] = arr[i];
        arr[i] = base;
        quickSort(arr, begin, i - 1, ascending); // 递归调用左半数组
        quickSort(arr, i + 1, end, ascending); // 递归调用右半数组
    }

    public static void main(String[] args) {
        int[] nums = {12, 4, 25, 47, 58, 34, 25, 9, 99, 26, 1, -13, 162, 10093, -66, -1};
        int[] temparr;
        //测试快速排序
        System.out.println("测试快速排序:");
        temparr = nums.clone();
        QuickSort.quickSort(temparr);
        //逆序排序
        //QuickSort.quickSort(temparr,false);
        System.out.println(Arrays.toString(temparr));
    }


}